#include "link_list.h"
#include <stdlib.h>
#include <stdio.h>
bool InitList_LinkList(LinkList *L)
{
    // 创建一个带头节点的单链表
    *L = (LNode *)malloc(sizeof(LNode));
    // 判断内存是否分配为null
    if (*L == NULL)
    {
        return false;
    }
    // 将头节点指针设置为空
    (*L)->next = NULL;
    return true;
}
bool ListEmpty_LinkList(LinkList L)
{
    // 直接判断头节点的next指针是不是空的就可以判断了
    return L->next == NULL;
}
int ListLength_LinkList(LinkList L)
{
    // 计算链表的长度可以使用循环和变量++的方式统计
    int length = 0;
    // 跳过头节点开始统计
    LNode *p = L->next;
    // p表示指向节点的指针，*p表示节点
    while (p != NULL)
    {
        length++;
        p = p->next;
    }
    return length;
}
bool GetElem_LinkList(LinkList L, int pos, int *elem)
{
    // 判断获取位置是否合法
    // 因为链表是动态的所以没有上限，但是有下限，
    // 就是不能小于1
    if (pos < 1)
    {
        return false;
    }
    // 直接找到头节点的指向的第一个节点
    LNode *p = L->next;
    int i = 1;
    // 如果指针p没有指向null并且还没有到达pos的位置
    // 就是使用循环一直遍历下去
    while (p != NULL && i < pos)
    {
        p = p->next;
        // 这个i也是关键，用来锁定pos的位置
        i++;
    }
    // 如果p ==null说明已经遍历完了还是没有找到，直接返回false
    if (p == NULL)
    {
        return false;
    }
    // 这种情况就是找到了
    // 将p指向节点的data赋值给elem
    // 为什么是*elem？因为不加*就是一个指针，
    // 指针只能用来装地址，如果加了*就是通过地址锁定里边的数据
    // 比如说我在宿舍里边，不加*只能装我的宿舍号，但是加上*就可以通过宿舍号找到我
    *elem = p->data;
    return true;
}
LNode *LocalElem_LinkList(LinkList L, int elem)
{
    LNode *p = L->next;
    while (p != NULL)
    {
        if (p->data == elem)
        {
            return p;
        }

        p = p->next;
    }
    return NULL;
}
bool InsertElem(LinkList *L, int pos, int elem)
{
    // 判断插入的位置是否合法，对于链表只需要判断一端
    if (pos < 1)
    {
        return false;
    }
    // 将头节点赋值给节点p，
    // L是一个二级指针，只有解引用了才是头节点
    LNode *p = *L;
    // 这个计数是因为要插到元素的前面，所以会少一位
    int i = 0;
    // 找到pos-1个节点
    while (p != NULL && i < pos - 1)
    {
        p = p->next;
        i++;
    }
    // 超出范围判断
    if (p == NULL)
    {
        return false;
    }
    // 为新节点分配空间
    LNode *newNode = (LNode *)malloc(sizeof(LNode));
    // 把数据装到newnode的数据域里边
    newNode->data = elem;
    // 将p节点的后继结点赋值给newnode的指针域
    newNode->next = p->next;
    // 将p的指针域指向newnode,实现p节点和p的后继结点的断开
    p->next = newNode;
    return true;
}
bool DeleteElem(LinkList *L, int pos, int *elem)
{
    // 判断位置是不是合法
    if (pos < 1)
    {
        return false;
    }
    // 创建一个零时节点指向头节点
    LNode *p = *L;
    int i = 0;
    // 找到pos-1个节点
    while (p->next != NULL && i < pos - 1)
    {
        p = p->next;
        i++;
    }
    // 判断位置超出范围
    if (p->next == NULL)
    {
        return false;
    }
    // 开始删除节点,删除节点的位置也通过前面的遍历找到了
    LNode *q = p->next;
    *elem = q->data;
    p->next = q->next;
    free(q);
    return true;
}
void PrintList_LinkList(LinkList L)
{
    // 创建一个临时节点指向头节点指向的第一个节点，
    // 也就是头节点的后继结点
    // 使用while循环，直到节点为NULL，也就是遍历完
    LNode *p = L->next;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
void DestoryList(LinkList *L)
{
    // 销毁链表需要一个一个销毁，
    // 从头节点开始销毁，这个L是指向头节点的指针
    LNode *p = *L;
    while (p != NULL)
    {
        LNode *temp = p;
        p = p->next;
        free(temp);
    }
    // 最后把指向头节点的指针置为NULL
    *L = NULL;
}
void CreateListHead(LinkList *L, int n)
{
    // 给头节点分配空间
    *L = (LNode *)malloc(sizeof(LNode));
    // 将头节点的指针域值为空
    (*L)->next = NULL;
    // 使用for循环配合malloc创建节点,这个n是创建节点的个数
    for (int i = 0; i < n; i++)
    {
        LNode *newNode = (LNode *)malloc(sizeof(LNode));
        newNode->data = i + 1;
        // 新节点指向头节点的后继结点，
        // 所有的新节点都是指向头节点的后继结点
        newNode->next = (*L)->next;
        //    新节点成为头节点的后继结点
        (*L)->next = newNode;
    }
}
void CreateListTail(LinkList *L, int n)
{
    *L = (LNode *)malloc(sizeof(LNode));
    // 先将头节点的指针域设置为null
    (*L)->next = NULL;
    // 设置一个尾指针指向头节点
    LNode *tail = *L;
    // 使用for循环创建头节点
    for (int i = 0; i < n; i++)
    {
        // 创建新节点
        LNode *newNode = (LNode *)malloc(sizeof(LNode));
        // 给新节点的数据域里边装东西
        newNode->data = i + 1;
        // 将新节点的指针域设置为null
        newNode->next = NULL;
        // 将尾节点的指针域指向新节点，
        // 建立尾节点和新节点之间的连接
        tail->next = newNode;
        // 尾指针指向新节点，
        // 维护尾指针的正确指向
        tail = newNode;
    }
}